perm filename COMPIL[BOO,JMC] blob
sn#534907 filedate 1980-09-14 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00009 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 .if false then begin "extracted from MACHIN"
C00010 00003 .if false then begin "notes"
C00012 00004 .s(COMPIL,COMPILING IN LISP)
C00015 00005 .ss(lap,Some facts about the PDP-10.)
C00026 00006 .ss(lapcode,Code produced by LISP compilers.)
C00031 00007 .NEXT PAGE
C00039 00008 .NEXT PAGE
C00054 00009 .NEXT PAGE
C00075 ENDMK
C⊗;
.if false then begin "extracted from MACHIN"
some ideas: abstract LAP to remove machine dependence.
write an interpreter for new LAP to explain semantics
give macros that will convert new LAP into the old LAP as
example of to make compiled code run.
.ss(compiling,Compiling.)
We will give examples of several LISP compilers in Chapter {SECTION COMPIL}.
Here we give just a brief introduction in order to discuss the interaction
of compiled and interpreted code and complete our picture of a LISP system.
The target language of a LISP compiler is a symbolic assembly language
called $LAP. Each $LAP program is a list of instructions and each instruction
is a list containing a symbolic operation code, and what ever address information
is needed. The important point to notice is that such programs are made up of
ordinary lists and thus can be generated by a LISP program. All that is
needed then is an assembler/loader to convert the assembly language program
into actual binary code and load it into memory (putting appropriate
$SUBR properties on the property lists of the atoms naming the compiled
programs).
There are two ways in which compiled code and interpreted code
might interact.
One is that if we have a collection of programs communicating through
some global variables then both the interpreter and the compiler may
need to know about these variables. Some implementations of LISP
have a value cell associated with each atom where the current value
is kept. Old bindings are kept on a stack to use for restoring when
λ's or qprogs are exited. In this case the loader can fill in the
location of the value cell for references to global variables.
If current values are kept on a stack then names will have to be kept too
and reference to a global variable will generate code to search the stack.
The second is that we may wish to have a compiled program
call an interpreted program. In general when a program is compiled
and a function application occurs in the program the compiler
will not know whether the function will be compiled or interpreted.
And in fact we may wish to switch horses in mid stream for various reasons
and thus not be committed to one mode of application or another.
The solution to the problem is as follows. A function call in a
compiled program jumps to a routine that looks up the
function definition just as the interpreter would and performs
the appropriate action depending on what kind of definition is found.
This interaction means that we can replace function definitions
and have the new version used by compiled as well as interpreted programs.
In particular we can trace compiled programs (using a special form of
⊗apply that takes a subroutine pointer rather than a lambda expression
as first argument). Also traced programs will be noticed by calling
compiled programs.
You may complain that we pay a large price in efficiency
for all this flexibility when the usual reason for compiling
is to make things run faster. LISP has a solution to this problem too.
Namely, it is possible to arrange for the compiled code to modify
itself when a call turns out to be to a compiled function so that
the next time that call is executed, the address is known and no
search for the definition is necessary. Of course if you run in this
mode a function that is redefined will not be noticed by a compiled
program calling this function. As you might imagine, there are various
intermediate modes and other clever solutions to the calling problem.
One fairly nice solution is to use a table with an entry
for each function. The compile code knows only the entry location.
The first time a function is called (by anyone) the corresponding
entry is filled in and any later calls go directly with only
a single level of indirection. At any point one or all entries
in the table can be erased. Then it appears as though the
function hadn't previously been called, and the entry is reset
at the next call.
.cb Exercise
.item←0
#. Add a feature to the trace package to trace compiled programs
($$SUBR$s). Note that you will have to do some additional work
to treat the arguments to a $$SUBR$ as they can't be obtained
from the pointer. You might require to user to say how many,
or assume that the function also has an $$NARGS$ property
which is the number of arguments required.
.end "extracted from MACHIN"
.if false then begin "notes"
Interaction of compiled and iterpreted code.
abstract description of LAP code
exercise LAP code optimization
fix LCOM4 to append lists of code and omit the flattening hack
Proof of correctness of LCOM0.
What to do with gensym? Pass parm down and back or pass sExp
with convention that cdr is kept at upper level, car may be diddled
at lower level. Effectively a unary repn of symbols. (see SCOM)
(Include one or two modified pieces of LCOM0 as example)
Suitable induction rule
How to handle recursion vs stack.
Think about improving LCOM4 to produce tail-recursive code
[from comments by V Pratt]
44,4-7 (To avoid this, which has nothing to do with compiling, how
about making the output a list? That should approximately halve
"file", which seems to be doing two different things anyway, unless
you consider DE to be something associated with files.)
[p42. comment about I/O mumbo-jumbo in "compl". Also a comment on
failure of BB to make itself understood as "file" is the argument
and not the fn name.]
.end "notes"
.s(COMPIL,COMPILING IN LISP)
.if NOTASSEMBLING then start
.COMPUT: NEXT SECTION!;
.end
Compiling is an important example of symbolic computation and
has received much study. Much of the study has been devoted
to parsing which is essentially the transformation of an input string
in the source language into an internal form. The internal form used
depends on the compiler. Sometimes it is Polish prefix or postfix notation,
sometimes it is list structure, and sometimes it consists of entries in
a collection of tables.
When internal notation LISP is being compiled, the parsing is
trivial, because the input is S-expressions and the internal form wanted
is list structure, so what parsing there is is done by the ordinary LISP
⊗read routine. Therefore, compilers can be very compact and
transparent in structure, and we can concentrate our attention on the code
generation phase. This is as it should be, because,
parsing is basically a side issue in compiling, and code generation is the
matter of main scientific interest.
We shall describe two compilers in this chapter called LCOM0 and
LCOM4 which compile S-expression LISP into machine language for the PDP-10
computer according to the conventions of MACLISP.
Before describing the
compilers, we must describe these conventions.
.ss(lap,Some facts about the PDP-10.)
The target language is called LAP for LISP assembly program. Each
function is compiled separately into a separate LAP program, and these
programs are written onto a disk file. These files can later be read into
a LISP core image and assembled in place by the LAP assembler which is
part of the LISP runtime routines. The compiler, on the other hand, is a
separate LISP core image that can be instructed to compile several input
files. For an input file called <name>, it produces an output file
called <name>.LAP. All this is specific to the time-sharing systems
for the PDP-10 and DECSYSTEM-20.
The LAP program produced is a list of words; the last word is qNIL,
and the first word is a header of the form $$(LAP ⊗fname SUBR)$ where
⊗fname is the name of the function compiled. This header tells the
DSKIN program that it should read S-expressions till it comes to qNIL and
then submit what it has collected to the LAP assembler which will assemble
it into core. The rest of the words are either atoms representing labels
or lists representing single PDP-10 instructions.
The following facts about the PDP-10 may be of use:
The PDP-10 has a 36 bit word and an 18 bit address. In
instructions and in accumulators used as index registers the address is
found in the right part of the word where the least significant bits in
arithmetic reside. The compilers we shall describe don't need to know
the word length, since this is handled by LAP.
There are 16 general registers which serve simultaneously as
accumulators (receiving the results of arithmetic operations), index
registers (modifying the nominal addresses of instructions to form
effective addresses), and as the first 16 registers of memory (if the
effective address of an instruction is less than 16, then the
instruction uses the corresponding general register as its operand.)
The fact that there are sixteen general registers is not known to the
compiler, but it will produce non-working code if it is given functions
to compile that have too many arguments.
All instructions have the same format and are written for the
LAP assembly program in the form
(<op name> <accumulator> <address> <index register>).
Thus $$(MOVE 1 3 P)$ causes accumulator__1 to receive the contents of
a memory register whose address is__3+c(P), i.e. 3+<the contents of
general register P>. <address> may be a number, a label, or an
S-expression constant in the form $$(QUOTE ⊗⊗e⊗)$ where ⊗e is an S-expression.
The latter allows a quoted S-expression to be loaded into accumulator__1
by the instruction $$(MOVEI_1_(QUOTE_⊗⊗e⊗))$. An addtional form that
appears in the address field for some instructions is
$$(α%_0_0_⊗m ⊗⊗m⊗)$ . This is a literal with value a word
containing ⊗m in the lefthand side and ⊗n in the righthand side.
Which form of <address> is meaningful depends on the instruction.
To determine the effective address of an instruction the following
rules apply. The value of <address> is combined with the contents of the
index register to form a direct address.
If no index register is specified, then just the value of <address> is used.
If an @ occurs in the list as a separate symbol, then the memory
reference is indirect, i.e. the effective address is the contents of
the right half of the word directly addressed by the instruction
(modified by the index register and indirect bit of that word).
In the following description of some instructions useful in constructing
the compiler, <ef> denotes the effective address of an instruction and ac
denotes the accumulator.
.SKIP
.BEGIN INDENT 8,30,8
.PREFACE 0
.AT 0 ⊂BREAK⊃
.AT 24 ⊂""⊃
.TURN ON "∂"
.VARIABLE I
.I ← 31
MOVE ∂(I)c(ac) ← c(<ef>)
MOVEI ∂(I)c(ac) ← <ef>
MOVEM ∂(I)c(<ef>) ← c(ac)
HLRZ ∂(I)right half of c(ac) ← left half of c(<ef>)
HRRZ ∂(I)right half of c(ac) ← right half of c(<ef>)
∂(16)(These two are used indirectly for _car_ and _cdr_ respectively.)
ADD ∂(I)c(ac) ← c(ac) + c(<ef>)
SUB ∂(I)c(ac) ← c(ac) - c(<ef>)
JRST ∂(I)go to <ef>
JUMPE ∂(I)if c(ac) = 0 then go to <ef>
JUMPN ∂(I)if c(ac) ≠ 0 then go to <ef>
CAME ∂(I)if c(ac) = c(<ef>) then <skip next instruction>
CAMN ∂(I)if c(ac) ≠ c(<ef>) then <skip next instruction>
PUSH ∂(I)c(c(right half of ac)) ← c(<ef>); the contents
of each half of ac is increased by one and if
the contents of the left half is then _0, a stack
overflow interrupt occurs. (PUSH P ac) is
used in LISP to put c(ac) on the
stack.
POP ∂(I)c(<ef>) ←c(c(right half of ac)); the
contents of each half of ac are then decreased
by 1. This may be used for removing the
top element of the stack. Thus (POP P 1) puts
the top element of the stack in accumulator 1.
The i-th element of the stack is obtained by
(MOVE 1 @ i P).
POPJ ∂(I)(POPJ P) is used for returning from a subroutine
.END
These instructions are adequate for compiling basic LISP code
with the addition of the subroutine calling pseudo-instrucion. The form
of this instruction is $$(CALL_⊗n (QUOTE_%1<subr>%*))$ .
It is used for calling the LISP subroutine <subr> with ⊗n
arguments. The convention is that the arguments will be stored in
successive accumulators beginning with accumulator _1, and the result
will be returned in accumulator__1. In particular the functions
$ATOM and $CONS are called with $$(CALL_1_(QUOTE_ATOM))$ and
$$(CALL_2_(QUOTE_CONS))$ respectively.
Programs produced by you will be
called similarly when their names are referred to.
The details of how $CALL works are unimportant here; it actually traps to
a machine language routine that checks whether the function is being traced
and which can replace the $CALL by $PUSHJ for greater speed when tracing
is definitely not wanted.
.if false then begin
There are minor modifications in the form of some of the instructions
for compiling code for the LISP1.6 assembler. These include the calling
instruction which has the form $$(CALL_⊗n (QUOTE_%1<subr>%*)_S)$ , the
form of the special literal which is $$(C_⊗m 0_⊗n 0)$ and the manner of
indicating indirect addressing, which is to attach the @ sign to the
operation name rather than putting in as a separate element of the list.
.end
.ss(lapcode,Code produced by LISP compilers.)
We will discuss two compilers, a simple one called LCOM0 and a
more optimising compiler called LCOM4. LCOM4 produces about half as many
instructions for a given function as does LCOM0. Besides these, there are
the standard PDP-10 LISP compiler written at M.I.T. by Richard Greenblatt
and Stuart Nelson and modified by Whitfield Diffie and the MACLISP compiler
NCOMPLR.
At the end of this section are
examples of the output of each of the compilers mentioned above
for the file containing:
.NOFILL
$$(DEFPROP DROP$
$$(LAMBDA(U)$
$$(COND ((NULL U) NIL) (T (CONS (LIST (CAR U)) (DROP (CDR U))))))$
$$EXPR)$
.FILL
The following comments are with regard to these examples.
1. Note that all four compilers produce the same first line of
heading. This is necessary for the LAP assembly program which also
requires the _qNIL_ at the end as punctuation. The standard compiler
and NCOMPLR also
use a function called _$XCONS_ that has the same effect as $CONS
except that it receives its arguments in the reverse order which is
sometimes convenient. This requires, of course, that the compiler be
smart enough to decide where it is more convenient to put the
arguments of the ⊗cons function. They also use $NCONS rather than $LIST
to form a list of one element.
2. The two compilers, LCOM0 and LCOM4, are similar in structure,
but LCOM4, the better
one, which is twice as long, uses the following optimisations.
2.1. When the argument of $CAR or $CDR is a variable, it compiles
a $$(HLRZ_1_@__⊗i P)$ or $$(HRRZ_1_@__⊗i P)$ which gets the result through the
stack without first compiling the argument into an accumulator.
2.2. When it has to set up the arguments of a function in the
accumulators, in general, the program must compute the arguments one
at a time and save them on the stack, and then load the accumulators
from the stack. However, if one of the arguments is a variable, is a
quoted expression, or can be obtained from a variable by a chain of
_$$CAR$s_ and _$$CDR$s, then it need not be computed until the time of
loading accumulators since it can be computed using only the
accumulator in which it is wanted.
3. The Diffie compiler produces about 10 percent less code
than LCOM4; the main difference seems to be that it sometimes notices
when it has an expression that it will need later. Sometimes this
feature leads it astray. For example, it may save _qa ⊗u _
for later use at greater cost than re-computing it.
4. NCOMPLR is noted particularly for its efficient code for
numerical computations. Hence the "N".
Except for some bookkeeping code initially, the Diffie compiler and
NCOMPLR produce similar code for this example.
.NEXT PAGE
******************************************************************
.SKIP 2
LCOM0 produces the following code for the MACLISP LAP assembler.
.BEGIN VERBATIM SELECT 6
(LAP DROP SUBR)
(PUSH P 1)
(MOVE 1 0 P)
(PUSH P 1)
(MOVE 1 0 P)
(SUB P (% 0 0 1 1))
(CALL 1 (QUOTE NULL))
(JUMPE 1 G0003)
(MOVEI 1 0)
(JRST 0 G0002)
G0003
(MOVEI 1 (QUOTE T))
(JUMPE 1 G0004)
(MOVE 1 0 P)
(PUSH P 1)
(MOVE 1 0 P)
(SUB P (% 0 0 1 1))
(CALL 1 (QUOTE CAR))
(PUSH P 1)
(MOVE 1 0 P)
(SUB P (% 0 0 1 1))
(CALL 1 (QUOTE LIST))
(PUSH P 1)
(MOVE 1 -1 P)
(PUSH P 1)
(MOVE 1 0 P)
(SUB P (% 0 0 1 1))
(CALL 1 (QUOTE CDR))
(PUSH P 1)
(MOVE 1 0 P)
(SUB P (% 0 0 1 1))
(CALL 1 (QUOTE DROP))
(PUSH P 1)
(MOVE 1 -1 P)
(MOVE 2 0 P)
(SUB P (% 0 0 2 2))
(CALL 2 (QUOTE CONS))
(JRST 0 G0002)
G0004
G0002
(SUB P (% 0 0 1 1))
(POPJ P)
NIL
.END
.SKIP TO LINE 1
******************************************************************
.SKIP 2
LCOM4 produces the following code for the MACLISP LAP assembler.
.BEGIN VERBATIM SELECT 6
(LAP DROP SUBR)
(PUSH P 1) ~save argument, U, on stack
(MOVE 1 0 P) ~get U off stack
(JUMPE 1 G0003) ~if U=NIL then exit
(HLRZ 1 @ 0 P) ~car U
(CALL 1 (QUOTE LIST)) ~<car U>
(PUSH P 1) ~save <car U>
(HRRZ @ 1 -1 P) ~cdr U (U now 1 below top of stack
(CALL 1 (QUOTE DROP)) ~drop cdr U
(MOVE 2 1) ~set up arguments for cons
(MOVE 1 0 P)
(SUB P (% 0 0 1 1)) ~reset stack to arglist
(CALL 2 (QUOTE CONS)) ~cons[<car u>,cdr U]
G0003
(SUB P (% 0 0 1 1)) ~reset stack to position at entry
(POPJ P) ~return
NIL
.END
******************************************************************
.SKIP 2
The Diffie compiler produces the following code for the LISP1.6 assembler.
.BEGIN VERBATIM SELECT 6
(LAP DROP SUBR)
(PUSH P 1)
(JUMPE 1 TAG1)
(HLRZ@ 1 0 P)
(CALL 1 (E NCONS) S)
(PUSH P 1)
(HRRZ@ 1 -1 P)
(CALL 1 (E DROP) S)
(POP P 2)
(CALL 2 (E XCONS) S)
TAG1 (SUB P (C O 0 1 1))
(POPJ P)
NIL
.END
.next page
******************************************************************
.SKIP 2
The MACLISP compiler, NCOMPLR, produces the following code:
(The pseudo-instruction ARGS tells the assembler the number of arguments
expected by the function. The instruction JSP is a special fast function call
done by jumping rather than going through the regular calling mechanism. T
denotes an accumulator designated to hold temporary values.)
.BEGIN VERBATIM SELECT 6
(LAP DROP SUBR)
(ARGS DROP (NIL . 1))
(PUSH P 1)
(JSP T PDLNMK)
(JUMPE 1 G0001)
(HLRZ 1 @ 0 P)
(JSP T %NCONS)
(PUSH P 1)
(HRRZ 1 @ -1 P)
(CALL 1 'DROP)
(POP P 2)
(JSP T %XCONS)
G0001
(SUB P (% 0 0 1 1))
(POPJ P)
NIL
.END
.NEXT PAGE
.ss(lcom0,LCOM0.)
The following is an annotated listing of the MACLISP version of
LCOM0 in external notation. A listing in internal notation can be found in
Appendix {SECTION LCOMap}.
⊗compl is the user-callable driver. It is a FEXPR. It takes as
an argument a single file name.
EXPRs on a file called FILNAM will be compiled into LAP and
written on the file FILNAM.LAP. Other types of function
definitions and non-definitions are simply copied to output.
It is, alas, dependent on the I/O structure of the implementation
and need not be studied carefully. All the other functions are
substantially independent of implementation.
.BEGIN nofill turnon "∂"
.n←8 m←55
∂(n) FEXPER:
∂(n) ⊗⊗compl file ← ⊗
∂(n) ⊗⊗ [uwrite[], ⊗ ∂(m)~Open a file for output
∂(n) ⊗⊗ apply[$$EREAD$, file], ⊗ ∂(m)~Open input file
∂(n) ⊗⊗ select-disk-input[⊗
∂(n) ⊗⊗ read-until-eof[with z do⊗ ∂(m)~Read each expression in file
∂(n) ⊗⊗ qif qa z = $$DEFUN$ ∨ [qa z = $$DEFPROP$ ∧ qaddd z = $$EXPR$] qthen ⊗
∂(n) ⊗⊗ [qprog [prog]⊗
!fcncompl&0 ∂(n) ⊗⊗ prog⊗
∂(n) ⊗⊗ ← [qif qa z = $$DEFUN$ qthen comp[qad z, qadd z, qaddd z]⊗
∂(n) ⊗⊗ qelse comp[qad z, qad qadd z, qadd qadd z]]⊗
∂(n) ⊗⊗ unselect-tty ⊗
∂(n) ⊗⊗ select-disk-output mapc[print, prog]⊗∂(m)~ Print code in file
∂(n) ⊗⊗ print <qad z, length prog>]⊗
∂(n) ⊗⊗ qelse unselect-tty select-disk-output print z], ⊗
∂(n) ⊗⊗ apply[$$UFILE$, <qa file, $$LAP$>], ⊗∂(m)~Close and name file
∂(n) ⊗⊗ $$ENDCOMP$]]⊗
.end
⊗comp compiles a single function definition, returning a list of
the LAP code corresponding to the definition.
⊗fn is the atomic name of the function being compiled.
⊗vars is the formal parameter list for the function.
⊗exp is the function body.
.begin nofill turnon "∂"
.n←8 m←50
.turnoff "{}"
∂(n) ⊗⊗comp[fn, vars, exp] ← ⊗
∂(n) ⊗⊗ {length vars}[λn: ⊗
∂(n) ⊗⊗ <<$$LAP$, fn, $$SUBR$>>⊗
!fcncomp&0 ∂(n) ⊗⊗ * mkpush[n, 1]⊗
∂(n) ⊗⊗ * compexp[exp, -n, prup[vars, 1]]⊗
∂(n) ⊗⊗ * <<$$SUB$, $$P$, <$$α%$, 0, 0, n, n>>>⊗
∂(n) ⊗⊗ * $$((POPJ P) qNIL)$]⊗
.end
⊗prup returns an a-list formed by pairing successive elements of
⊗vars with consecutive integers beginning with ⊗n.
.begin nofill turnon "∂"
.n←8 m←50
∂(n) ⊗⊗prup[vars, n] ← ⊗
!fcnprup&0 ∂(n) ⊗⊗ qif qn vars qthen qNIL qelse [qa vars . n] . prup[qd vars, add1 n]⊗
.end
⊗mkpush returns a list of ⊗n $$(PUSH P ⊗⊗i⊗)$ instructions, where ⊗i runs
from ⊗n to ⊗m+n-1. It is used to push arguments onto the stack.
.begin nofill turnon "∂"
.n←8 m←50
∂(n) ⊗⊗mkpush[n, m] ← ⊗
!fcnmkpush&0 ∂(n) ⊗⊗ qif n < m qthen qNIL qelse <$$PUSH$, $$P$, m> . mkpush[n, add1 m]⊗
.end
⊗compexp is the heart of LCOM0. It determines precisely
what an expression is, and compiles appropriate code
for it. It returns a list of that code.
⊗exp is the expression to be compiled.
⊗m is minus the number of entries on the stack. When
added to a value retrieved from the A-LIST ⊗vpr, it
can be used to locate a variable on the stack.
⊗vpr is an A-LIST, associating variable names with
numbers which, when added to ⊗m, give stack offsets.
Both ⊗m and ⊗vpr maintain these definitions throughout.
⊗gensym[] is a pseudo-function of no arguments. Every time it is called,
it returns a different symbol. The presence of ⊗gensym[] means that
LCOM0 and LCOM4 are not pure LISP so that the techniques of Chapter 3
cannot be used to prove that they meet their specifications. It is
possible to eliminate the use of ⊗gensym, but as of the present writing,
such version hasn't been written. In any case, other unsolved problems
remain before one can give a first order logic proof of the correspondence
between ⊗eval and the code produced by the compilers.
.begin nofill turnon "∂"
.n←8 m←62
.turnoff "{}"
∂(n) ⊗⊗compexp[exp, m, vpr] ← ⊗
∂(n) ⊗⊗ qif qn exp qthen $$((MOVEI 1 0))$⊗ ∂(m)~qNIL
∂(n) ⊗⊗ qelse qif exp = qT qthen $$((MOVEI 1 (QUOTE qT)))$⊗ ∂(m)~qT
∂(n) ⊗⊗ qelse qif numberp exp qthen <<$$MOVEI$, 1, <$$QUOTE$, exp>>>⊗ ∂(m)~number
∂(n) ⊗⊗ qelse qif qat exp qthen <<$$MOVE$, 1, m + qd assoc[exp, vpr], $$P$>>⊗∂(m)~variable
∂(n) ⊗⊗ qelse qif qa exp = $$AND$ ∨ qa exp = $$OR$ ∨ qa exp = $$NOT$ qthen ⊗∂(m)~boolean expression
∂(n) ⊗⊗ {gensym[], gensym[]}[λl1, l2: ⊗
∂(n) ⊗⊗ combool[exp, m, l1, qNIL, vpr]⊗
∂(n) ⊗⊗ * <$$(MOVEI 1 (QUOTE qT))$, ⊗
∂(n) ⊗⊗ <$$JRST$, 0, l2>, ⊗
∂(n) ⊗⊗ l1, ⊗
∂(n) ⊗⊗ $$(MOVEI 1 0)$, ⊗
∂(n) ⊗⊗ l2>]⊗
∂(n) ⊗⊗ qelse qif qa exp = $$COND$ qthen comcond[qd exp, m, gensym[], vpr]⊗ ∂(m)~$COND
!fcncompexp&0 ∂(n) ⊗⊗ qelse qif qa exp = $$QUOTE$ qthen <<$$MOVEI$, 1, exp>>⊗ ∂(m)~$QUOTE
∂(n) ⊗⊗ qelse qif qat qa exp qthen ⊗ ∂(m)~function call
∂(n) ⊗⊗ {length qd exp}[λn: ⊗
∂(n) ⊗⊗ complis[qd exp, m, vpr]⊗
∂(n) ⊗⊗ * loadac[1 - n, 1]⊗
∂(n) ⊗⊗ * <<$$SUB$, $$P$, <$$α%$, 0, 0, n, n>>>⊗
∂(n) ⊗⊗ * <<$$CALL$, n, <$$QUOTE$, qa exp>>>]⊗
∂(n) ⊗⊗ qelse qif qaa exp = $$LAMBDA$ qthen ⊗ ∂(m)~λ-expression
∂(n) ⊗⊗ {length qd exp}[λn: ⊗
∂(n) ⊗⊗ complis[qd exp, m, vpr]⊗
∂(n) ⊗⊗ * compexp[qadda exp, m - n, prup[qada exp, 1 - m] * vpr]⊗
∂(n) ⊗⊗ * <<$$SUB$, $$P$, <$$α%$, 0, 0, n, n>>>]⊗
∂(n) ⊗⊗ qelse qNIL⊗ ∂(m)~oops!
.end
⊗complis compiles code to evaluate each expression in a list of
expressions and to push those values onto the stack. It
returns a list of that code. It is used to compile code
to evaluate arguments to called functions or λ-expressions.
⊗u is a list of expressions.
.begin nofill turnon "∂"
.n←8 m←50
∂(n) ⊗⊗complis[u, m, vpr] ← ⊗
∂(n) ⊗⊗ qif qn u qthen qNIL⊗
!fcncomplis&0 ∂(n) ⊗⊗ qelse compexp[qa u, m, vpr]⊗
∂(n) ⊗⊗ * $$((PUSH P 1))$⊗
∂(n) ⊗⊗ * complis[qd u, sub1 m, vpr]⊗
.end
⊗loadac returns a list of $$(MOVE ⊗i ⊗j P)$ instructions, loading
consecutive accumulators from the top of the stack.
⊗k indexes the accumulator loaded.
⊗n indexes the stack offset.
.begin nofill turnon "∂"
.n←8 m←50
∂(n) ⊗⊗loadac[n, k] ← ⊗
!fcnloadac&0 ∂(n) ⊗⊗ qif n > 0 qthen qNIL⊗
∂(n) ⊗⊗ qelse <$$MOVE$, k, n, $$P$> . loadac[add1 n, add1 k]⊗
.end
⊗comcond compiles a $COND.
⊗u is a list of clauses in the $COND.
⊗l is a label to be emitted at the end of all code for
the $COND.
.begin nofill turnon "∂"
.n←8 m←50
.turnoff "{}"
∂(n) ⊗⊗comcond[u, m, l, vpr] ← ⊗
∂(n) ⊗⊗ qif qn u qthen <l>⊗
∂(n) ⊗⊗ qelse {gensym[]}[λl1: ⊗
!fcncomcond&0 ∂(n) ⊗⊗ combool[qaa u, m, l1, qNIL, vpr]⊗
∂(n) ⊗⊗ * compexp[qada u, m, vpr]⊗
∂(n) ⊗⊗ * <<$$JRST$, 0, l>, l1>⊗
∂(n) ⊗⊗ * comcond[qd u, m, l, vpr]]⊗
.end
⊗combool compiles code for a single propositional expression.
That is, the
code generated evaluates the expression and branches somewhere,
according to whether its value is true or false.
⊗p is the propositional expression.
⊗l is a label which represents the branch point.
⊗flg is a flag. If ⊗flg is qNIL, code is to fall thru on non-qNIL
result and branch to ⊗l on qNIL result. If ⊗flg is non-qNIL,
code is to fall thru on qNIL result and branch to ⊗l on
non-qNIL result.
.begin nofill turnon "∂"
.n←8 m←62
.turnoff "{}"
∂(n) ⊗⊗combool[p, m, l, flg, vpr] ← ⊗
∂(n) ⊗⊗ qif qat p qthen ⊗ ∂(m) ~simple variable
∂(n) ⊗⊗ [compexp[p, m, vpr]⊗
∂(n) ⊗⊗ * <<qif flg qthen $$JUMPN$ qelse $$JUMPE$, 1, l>>]⊗
∂(n) ⊗⊗ qelse qif qa p = $$AND$ qthen ⊗ ∂(m)~conjunction
∂(n) ⊗⊗ [qif ¬flg qthen compandor[qd p, m, l, qNIL, vpr]⊗
∂(n) ⊗⊗ qelse {gensym[]}[λl1: ⊗
∂(n) ⊗⊗ compandor[qd p, m, l1, qNIL, vpr]⊗
!fcncombool&0 ∂(n) ⊗⊗ * <<$$JRST$, 0, l>>⊗
∂(n) ⊗⊗ * <l1>]]⊗
∂(n) ⊗⊗ qelse qif qa p = $$OR$ qthen ⊗ ∂(m)~disjunction
∂(n) ⊗⊗ [qif flg qthen compandor[qd p, m, l, qT, vpr]⊗
∂(n) ⊗⊗ qelse {gensym[]}[λl1: ⊗
∂(n) ⊗⊗ compandor[qd p, m, l1, qT, vpr] * <<$$JRST$, 0, l>> * <l1>]]⊗
∂(n) ⊗⊗ qelse qif qa p = $$NOT$ qthen combool[qad p, m, l, ¬flg, vpr]⊗ ∂(m)~negation
∂(n) ⊗⊗ qelse compexp[p, m, vpr]⊗ ∂(m)~other expression
∂(n) ⊗⊗ * <<qif flg qthen $$JUMPN$ qelse $$JUMPE$, 1, l>>⊗
.end
⊗compandor compiles code for lists of predicates connected
conjunctively or disjunctively.
⊗u is a list of predicates.
⊗l is a label.
⊗flg is a flag. If ⊗flg is qNIL, we are to fall thru on non-qNIL
results and branch to ⊗l on qNIL results ($AND case). If ⊗flg
is non-qNIL, we are to fall thru on qNIL results and branch
to ⊗l on non-qNIL results ($OR case).
.begin nofill turnon "∂"
.n←8 m←50
∂(n) ⊗⊗compandor[u, m, l, flg, vpr] ← ⊗
∂(n) ⊗⊗ qif qn u qthen qNIL⊗
!fcncompandor&0 ∂(n) ⊗⊗ qelse combool[qa u, m, l, flg, vpr]⊗
∂(n) ⊗⊗ * compandor[qd u, m, l, flg, vpr]⊗
.end
.NEXT PAGE
.ss(lcom4,LCOM4.)
.SKIP
The following is a listing in external notation of the MACLISP version
of the compiler LCOM4. A listing in internal notation can be found in
Appendix_{SECTION LCOMap}.
Comments are added where this compiler differs from LCOM0.
The main difference has to do with the classification of expressions into
five classes that can be compiled differently for greater efficiency. The five
classes are defined as follows:
.begin nofill turnon "∂"
.n←8 m←50
0. constants qNIL, qT, and numbers,
1. variables -- any atom not considered a constant,
2. quoted S-expressions -- non-atomic constants,
3. ⊗car - ⊗cdr chains applied to a variable,
4. all others, except
5. the last class 4 element in the argument list.
FEXPR:
∂(n) ⊗⊗compl file ← ⊗
∂(n) ⊗⊗ [uwrite[], ⊗
∂(n) ⊗⊗ apply[$$EREAD$, file], ⊗
∂(n) ⊗⊗ select-disk-input[⊗
∂(n) ⊗⊗ read-until-eof[with z do⊗
∂(n) ⊗⊗ qif qa z = $$DEFUN$ ∨ [qa z = $$DEFPROP$ ∧ qaddd z = $$EXPR$] qthen ⊗
∂(n) ⊗⊗ [qprog [prog]⊗
!fcncoompl&4 ∂(n) ⊗⊗ prog⊗
∂(n) ⊗⊗ ← [qif qa z = $$DEFUN$ qthen comp[qad z, qadd z, qaddd z]⊗
∂(n) ⊗⊗ qelse comp[qad z, qad qadd z, qadd qadd z]]⊗
∂(n) ⊗⊗ unselect-tty ⊗
∂(n) ⊗⊗ select-disk-output mapc[print, prog]⊗
∂(n) ⊗⊗ print <qad z, length prog>]⊗
∂(n) ⊗⊗ qelse unselect-tty select-disk-output print z], ⊗
∂(n) ⊗⊗ apply[$$UFILE$, <qa file, $$LAP$>], ⊗
∂(n) ⊗⊗ $$ENDCOMP$]]⊗
.end
Instead of ⊗⊗append⊗ing the instructions into a list like ⊗compexp of
LCOM0 does, LCOM4 ⊗⊗cons⊗es
them into a tree form and flattens the final version into a list. In order that
the items of the tree form all have the structure of a list of atoms, labels and
the end mark qNIL are put in a list flagged by $LABEL and extracted by ⊗flat.
The hope was to make the compiler faster by omitting all the calls to ⊗append
but it does not seem to have made a lot of difference.
.begin nofill turnon "∂"
.n←8 m←50
.turnoff "{}"
∂(n) ⊗⊗comp[fn, vars, exp] ← ⊗
∂(n) ⊗⊗ {prup[vars, 1], length vars}[λvpr, n: ⊗
∂(n) ⊗⊗ flat[<<<$$LAP$, fn, $$SUBR$>>, ⊗
∂(n) ⊗⊗ mkpush[n, 1], ⊗
!fcncomp&4 ∂(n) ⊗⊗ compexp[exp, -n, vpr], ⊗
∂(n) ⊗⊗ substack n, ⊗
∂(n) ⊗⊗ $$((POPJ P) (LABEL qNIL))$>, ⊗
∂(n) ⊗⊗ qNIL]]⊗
∂(n) ⊗⊗flat[u, s] ← ⊗
∂(n) ⊗⊗ qif qn u qthen s⊗
∂(n) ⊗⊗ qelse qif qn qa u qthen flat[qd u, s]⊗
!fcnflat&4 ∂(n) ⊗⊗ qelse qif qa u = $$LABEL$ qthen qad u . s⊗
∂(n) ⊗⊗ qelse qif qat qa u qthen u . s⊗
∂(n) ⊗⊗ qelse flat[qa u, flat[qd u, s]]⊗
.end
⊗substack creates code to move down the stack, but creates no code for
the case ⊗n = 0 which is a no-op.
.begin nofill turnon "∂"
.n←8 m←60
.turnoff "{}"
∂(n) ⊗⊗substack n ← ⊗
!fcnsubstack&4 ∂(n) ⊗⊗ qif n = 0 qthen qNIL qelse <<$$SUB$, $$P$, <$$α%$, 0, 0, n, n>>>⊗
∂(n) ⊗⊗prup[vars, n] ← ⊗
!fcnprup&4 ∂(n) ⊗⊗ qif qn vars qthen qNIL qelse [qa vars . n] . prup[qd vars, add1 n]⊗
∂(n) ⊗⊗mkpush[n, m] ← ⊗
!fcnmkpush&4 ∂(n) ⊗⊗ qif n < m qthen qNIL qelse <$$PUSH$, $$P$, m> . mkpush[n, add1 m]⊗
∂(n) ⊗⊗compexp[exp, m, vpr] ← ⊗
∂(n) ⊗⊗ qif qn exp qthen $$((MOVEI 1 0))$⊗
∂(n) ⊗⊗ qelse qif exp = qT ∨ numberp exp qthen ⊗
∂(n) ⊗⊗ <<$$MOVEI$, 1, <$$QUOTE$, exp>>>⊗
∂(n) ⊗⊗ qelse qif qat exp qthen <<$$MOVE$, 1, m + qd assoc[exp, vpr], $$P$>>⊗
∂(n) ⊗⊗ qelse qif qa exp = $$CAR$ qthen ⊗ ∂(m)~compute ⊗car directly
∂(n) ⊗⊗ [qif qat qad exp qthen ⊗
∂(n) ⊗⊗ <<$$HLRZ$, 1, $$@$, m + qd assoc[qad exp, vpr], $$P$>>⊗
∂(n) ⊗⊗ qelse <compexp[qad exp, m, vpr], $$((HLRZ 1 @ 1))$>]⊗
∂(n) ⊗⊗ qelse qif qa exp = $$CDR$ qthen ⊗ ∂(m)~compute ⊗cdr directly
∂(n) ⊗⊗ [qif qat qad exp qthen ⊗
∂(n) ⊗⊗ <<$$HRRZ$, 1, $$@$, m + qd assoc[qad exp, vpr], $$P$>>⊗
∂(n) ⊗⊗ qelse <compexp[qad exp, m, vpr], $$((HRRZ 1 @ 1))$>]⊗
∂(n) ⊗⊗ qelse qif qa exp = $$AND$ ∨ qa exp = $$OR$ ∨ qa exp = $$NOT$ ∨ qa exp = $$EQ$⊗
∂(n) ⊗⊗ qthen {gensym[], gensym[]}[λl1, l2: ⊗
∂(n) ⊗⊗ <combool[exp, m, l1, qNIL, vpr], ⊗
!fcncompexp&4 ∂(n) ⊗⊗ <$$(MOVEI 1 (QUOTE qT))$, ⊗
∂(n) ⊗⊗ <$$JRST$, 0, l2>, ⊗
∂(n) ⊗⊗ <$$LABEL$, l1>, ⊗
∂(n) ⊗⊗ $$(MOVEI 1 0)$, ⊗
∂(n) ⊗⊗ <$$LABEL$, l2>>>]⊗
∂(n) ⊗⊗ qelse qif qa exp = $$COND$ qthen comcond[qd exp, m, gensym[], vpr]⊗
∂(n) ⊗⊗ qelse qif qa exp = $$QUOTE$ qthen <<$$MOVEI$, 1, exp>>⊗
∂(n) ⊗⊗ qelse qif qat qa exp qthen ⊗ ∂(m)~uses improved
∂(n) ⊗⊗ <complisa[qd exp, m, vpr], ⊗∂(m)~argument evaluation
∂(n) ⊗⊗ <<$$CALL$, length qd exp, <$$QUOTE$, qa exp>>>>⊗
∂(n) ⊗⊗ qelse qif qaa exp = $$LAMBDA$ qthen ⊗
∂(n) ⊗⊗ {length qd exp}[λn: ⊗
∂(n) ⊗⊗ <stackup[qd exp, m, vpr], ⊗
∂(n) ⊗⊗ compexp[qadda exp, m - n, prup[qada exp, 1 - m] * vpr], ⊗
∂(n) ⊗⊗ substack n>]⊗
∂(n) ⊗⊗ qelse qNIL⊗
∂(n) ⊗⊗stackup[u, m, vpr] ← ⊗ ∂(m)⊗~ ≡ ⊗complis of LCOM0.
∂(n) ⊗⊗ qif qn u qthen qNIL⊗
!fcnstackup&4 ∂(n) ⊗⊗ qelse <compexp[qa u, m, vpr], ⊗
∂(n) ⊗⊗ $$((PUSH P 1))$, ⊗
∂(n) ⊗⊗ stackup[qd u, sub1 m, vpr]>⊗
.end
⊗ccchain test whether an expression is a ⊗car - ⊗cdr chain applied to a
variable.
.begin nofill turnon"∂"
.n←8 m←50
∂(n) ⊗⊗ccchain exp ← ⊗
!fcnccchain&4 ∂(n) ⊗⊗ [qa exp = $$CAR$ ∨ qa exp = $$CDR$] ∧ [qat qad exp ∨ ccchain qad exp]⊗
.end
⊗compc generates code (in reverse order) to load the value of a
⊗car - ⊗cdr chain into the accumulator designated by ⊗n2.
.begin nofill turnon"∂"
.n←8 m←50
∂(n) ⊗⊗compc[exp, n2, m, vpr] ← ⊗
∂(n) ⊗⊗ qif qat exp qthen error $$COMPC$⊗
∂(n) ⊗⊗ qelse qif qa exp = $$CAR$ qthen ⊗
∂(n) ⊗⊗ [qif qat qad exp qthen ⊗
!fcncompc&4 ∂(n) ⊗⊗ <<$$HLRZ$, n2, $$@$, m + qd assoc[qad exp, vpr], $$P$>>⊗
∂(n) ⊗⊗ qelse <$$HLRZ$, n2, $$@$, n2> . compc[qad exp, n2, m, vpr]]⊗
∂(n) ⊗⊗ qelse qif qat qad exp qthen ⊗
∂(n) ⊗⊗ <<$$HRRZ$, $$@$, n2, m + qd assoc[qad exp, vpr], $$P$>>⊗
∂(n) ⊗⊗ qelse <$$HRRZ$, n2, $$@$, n2> . compc[qad exp, n2, m, vpr]⊗
.end
⊗comcond is essentially the same as in LCOM0. It optimizes by considering
the special cases where the next clause in the list of arguments to $COND
is of the form $$((NULL_⊗⊗e⊗)_NIL)$ or $$(T_⊗⊗e⊗)$ for some expression ⊗e.
.begin nofill turnon"∂"
.n←8 m←50
.turnoff "{}"
∂(n) ⊗⊗comcond[u, m, l, vpr] ← ⊗
∂(n) ⊗⊗ qif qn u qthen <<$$LABEL$, l>>⊗
∂(n) ⊗⊗ qelse qif ¬qat qaa u ∧ qaaa u = $$NULL$ ∧ qn qada u qthen ⊗
∂(n) ⊗⊗ <compexp[qadaa u, m, vpr], ⊗
∂(n) ⊗⊗ <<$$JUMPE$, 1, l>>, ⊗
∂(n) ⊗⊗ comcond[qd u, m, l, vpr]>⊗
!fcncomcond&4 ∂(n) ⊗⊗ qelse qif qaa u = qT qthen <compexp[qada u, m, vpr], <<$$LABEL$, l>>>⊗
∂(n) ⊗⊗ qelse {gensym[]}[λl1: ⊗
∂(n) ⊗⊗ <combool[qaa u, m, l1, qNIL, vpr], ⊗
∂(n) ⊗⊗ compexp[qada u, m, vpr], ⊗
∂(n) ⊗⊗ <<$$JRST$, 0, l>, <$$LABEL$, l1>>, ⊗
∂(n) ⊗⊗ comcond[qd u, m, l, vpr]>]⊗
.end
⊗complisa classifies the expressions on the argument list ⊗u,
calls ⊗complis to generate code for those arguments which must be
computed and stored on the stack, ⊗loadac to generate code for
loading the accumulators and ⊗substack to generate code to restore the stack.
.begin nofill turnon"∂"
.n←8 m←50
.turnoff "{}"
∂(n) ⊗⊗complisa[u, m, vpr] ← ⊗
∂(n) ⊗⊗ {classify u}[λz: ⊗
!fcncomplisa&4 ∂(n) ⊗⊗ <complis[z, m, 1, vpr], ⊗
∂(n) ⊗⊗ loadac[z, 1 - ccount z, 1, m - ccount z, vpr], ⊗
∂(n) ⊗⊗ substack ccount z>]⊗
.end
⊗ccount of a list of classified expressions is the number of expressions
on the list of class 4. That is the number of values that will have to be
stacked when evaluating ⊗z as an argument list.
.begin nofill turnon"∂"
.n←8 m←50
∂(n) ⊗⊗ccount z ← ⊗
∂(n) ⊗⊗ qif qn z qthen 0⊗
!fcnccount&4 ∂(n) ⊗⊗ qelse qif qaa z = 4 qthen add1 ccount qd z⊗
∂(n) ⊗⊗ qelse ccount qd z⊗
.end
⊗loadac compiles code to load accumulators ⊗n2 and up with the values
of the expressions on the list ⊗z of classified expressions. ⊗m2 is the
stack offset for the value of the next class 4 expression on the list.
.begin nofill turnon"∂"
.n←8 m←50
∂(n) ⊗⊗loadac[z, m2, n2, m, vpr] ← ⊗
∂(n) ⊗⊗ qif qn z qthen qNIL⊗
∂(n) ⊗⊗ qelse qif qaa z = 1 qthen ⊗
∂(n) ⊗⊗ <$$MOVE$, n2, m + qd assoc[qda z, vpr], $$P$>⊗
∂(n) ⊗⊗ . loadac[qd z, m2, add1 n2, m, vpr]⊗
∂(n) ⊗⊗ qelse qif qaa z = 0 qthen ⊗
∂(n) ⊗⊗ <$$MOVEI$, n2, <$$QUOTE$, qda z>>⊗
∂(n) ⊗⊗ . loadac[qd z, m2, add1 n2, m, vpr]⊗
!fcnloadac&4 ∂(n) ⊗⊗ qelse qif qaa z = 2 qthen ⊗
∂(n) ⊗⊗ <$$MOVEI$, n2, qda z> . loadac[qd z, m2, add1 n2, m, vpr]⊗
∂(n) ⊗⊗ qelse qif qaa z = 3 qthen ⊗
∂(n) ⊗⊗ <reverse compc[qda z, n2, m, vpr], ⊗
∂(n) ⊗⊗ loadac[qd z, m2, add1 n2, m, vpr]>⊗
∂(n) ⊗⊗ qelse qif qaa z = 5 qthen loadac[qd z, 1, add1 n2, m, vpr]⊗
∂(n) ⊗⊗ qelse <$$MOVE$, n2, m2, $$P$>⊗
∂(n) ⊗⊗ . loadac[qd z, add1 m2, add1 n2, m, vpr]⊗
.end
⊗complis generates code to stack the values of the class 4 expressions
on the list of classified expressions ⊗z. ⊗k is the accumulator where the
next value should go. The last class_4 expression is marked class_5. When
this is evaluated it is loaded directly rather than being stacked. If a
class_5 expression is encountered, ⊗complis can quit as it has no more work.
.begin nofill turnon"∂"
.n←8 m←50
∂(n) ⊗⊗complis[z, m, k, vpr] ← ⊗
∂(n) ⊗⊗ qif qn z qthen qNIL⊗
∂(n) ⊗⊗ qelse qif qaa z = 4 qthen ⊗
∂(n) ⊗⊗ <compexp[qda z, m, vpr], ⊗
∂(n) ⊗⊗ $$((PUSH P 1))$, ⊗
!fcncomplis&4 ∂(n) ⊗⊗ complis[qd z, sub1 m, add1 k, vpr]>⊗
∂(n) ⊗⊗ qelse qif qaa z = 5 qthen ⊗
∂(n) ⊗⊗ <compexp[qda z, m, vpr], ⊗
∂(n) ⊗⊗ qif k = 1 qthen qNIL qelse <<$$MOVE$, k, 1>>>⊗
∂(n) ⊗⊗ qelse complis[qd z, m, add1 k, vpr]⊗
.end
⊗classify takes a list of expressions and returns a corresponding list
of classified expressions of the form [⊗n . ⊗e] where ⊗n is the class of ⊗e
according to the rules given at the beginning of the listing. The last
class_4 expression on the list is numbered 5.
.begin nofill turnon"∂"
.n←8 m←50
!fcnclassify&4 ∂(n) ⊗⊗classify u ← class2[class1[u, qNIL], qNIL, qT]⊗
∂(n) ⊗⊗class1[u, v] ← ⊗
∂(n) ⊗⊗ qif qn u qthen v⊗
∂(n) ⊗⊗ qelse qif qat qa u qthen ⊗
∂(n) ⊗⊗ [qif qa u = qNIL ∨ qa u = qT ∨ numberp qa u qthen ⊗
!fcnclass1&4 ∂(n) ⊗⊗ class1[qd u, [0 . qa u] . v]⊗
∂(n) ⊗⊗ qelse class1[qd u, [1 . qa u] . v]]⊗
∂(n) ⊗⊗ qelse qif qaa u = $$QUOTE$ qthen class1[qd u, [2 . qa u] . v]⊗
∂(n) ⊗⊗ qelse qif ccchain qa u qthen class1[qd u, [3 . qa u] . v]⊗
∂(n) ⊗⊗ qelse class1[qd u, [4 . qa u] . v]⊗
∂(n) ⊗⊗class2[u, v, flg] ← ⊗
∂(n) ⊗⊗ qif qn u qthen v⊗
!fcnclass2&4 ∂(n) ⊗⊗ qelse qif flg ∧ qaa u = 4 qthen class2[qd u, [5 . qda u] . v, qNIL]⊗
∂(n) ⊗⊗ qelse class2[qd u, qa u . v, flg]⊗
!fcnmkjrst&4 ∂(n) ⊗⊗mkjrst l ← <<$$JRST$, 0, l>>⊗
.end
⊗combool is essentially the same as in LCOM0 except it treats additional
special cases where ⊗p is of the form qT, $$(EQ ⊗e1 ⊗⊗e2⊗)$, or $$(NULL ⊗⊗e⊗)$.
It also handles the jumping somewhat differently using two versions of
⊗compandor.
.begin nofill turnon"∂"
.n←8 m←50
.turnoff "{}"
∂(n) ⊗⊗combool[p, m, l, flg, vpr] ← ⊗
∂(n) ⊗⊗ qif p = qT qthen [qif flg qthen mkjrst l qelse qNIL]⊗
∂(n) ⊗⊗ qelse qif qat p qthen ⊗
∂(n) ⊗⊗ <compexp[p, m, vpr], ⊗
∂(n) ⊗⊗ <<qif flg qthen $$JUMPN$ qelse $$JUMPE$, 1, l>>>⊗
∂(n) ⊗⊗ qelse qif qa p = $$EQ$ qthen ⊗
∂(n) ⊗⊗ <complisa[qd p, m, vpr], ⊗
∂(n) ⊗⊗ qif flg qthen $$((CAMN 1 2))$ qelse $$((CAME 1 2))$, ⊗
∂(n) ⊗⊗ mkjrst l>⊗
∂(n) ⊗⊗ qelse qif qa p = $$AND$ qthen ⊗
∂(n) ⊗⊗ [qif ¬flg qthen compandor[qd p, m, l, qNIL, vpr]⊗
!fcncombool&4 ∂(n) ⊗⊗ qelse {gensym[]}[λl1: ⊗
∂(n) ⊗⊗ <compandor1[qd p, m, l1, l, qNIL, vpr], <<$$LABEL$, l1>>>]]⊗
∂(n) ⊗⊗ qelse qif qa p = $$OR$ qthen ⊗
∂(n) ⊗⊗ [qif flg qthen compandor[qd p, m, l, qT, vpr]⊗
∂(n) ⊗⊗ qelse {gensym[]}[λl1: ⊗
∂(n) ⊗⊗ <compandor1[qd p, m, l1, l, qT, vpr], <<$$LABEL$, l1>>>]]⊗
∂(n) ⊗⊗ qelse qif qa p = $$NOT$ qthen combool[qad p, m, l, ¬flg, vpr]⊗
∂(n) ⊗⊗ qelse qif qa p = $$NULL$ qthen ⊗
∂(n) ⊗⊗ <compexp[qad p, m, vpr], ⊗
∂(n) ⊗⊗ <<qif flg qthen $$JUMPE$ qelse $$JUMPN$, 1, l>>>⊗
∂(n) ⊗⊗ qelse <compexp[p, m, vpr], ⊗
∂(n) ⊗⊗ <<qif flg qthen $$JUMPN$ qelse $$JUMPE$, 1, l>>>⊗
∂(n) ⊗⊗compandor[u, m, l, flg, vpr] ← ⊗
∂(n) ⊗⊗ qif qn u qthen qNIL⊗
!fcncompandor&4 ∂(n) ⊗⊗ qelse <combool[qa u, m, l, flg, vpr], ⊗
∂(n) ⊗⊗ compandor[qd u, m, l, flg, vpr]>⊗
∂(n) ⊗⊗compandor1[u, m, l, l2, flg, vpr] ← ⊗
∂(n) ⊗⊗ qif qn u qthen mkjrst l2⊗
!fcncompandor1&4 ∂(n) ⊗⊗ qelse qif qn qd u qthen combool[qa u, m, l2, ¬flg, vpr]⊗
∂(n) ⊗⊗ qelse <combool[qa u, m, l, flg, vpr], ⊗
∂(n) ⊗⊗ compandor1[qd u, m, l, l2, flg, vpr]>⊗
.end